Search results for "Catalan numbers"
showing 2 items of 2 documents
The pruning-grafting lattice of binary trees
2008
AbstractWe introduce a new lattice structure Bn on binary trees of size n. We exhibit efficient algorithms for computing meet and join of two binary trees and give several properties of this lattice. More precisely, we prove that the length of a longest (resp. shortest) path between 0 and 1 in Bn equals to the Eulerian numbers 2n−(n+1) (resp. (n−1)2) and that the number of coverings is (2nn−1). Finally, we exhibit a matching in a constructive way. Then we propose some open problems about this new structure.
Higher genera Catalan numbers and Hirota equations for extended nonlinear Schrödinger hierarchy
2021
We consider the Dubrovin--Frobenius manifold of rank $2$ whose genus expansion at a special point controls the enumeration of a higher genera generalization of the Catalan numbers, or, equivalently, the enumeration of maps on surfaces, ribbon graphs, Grothendieck's dessins d'enfants, strictly monotone Hurwitz numbers, or lattice points in the moduli spaces of curves. Liu, Zhang, and Zhou conjectured that the full partition function of this Dubrovin--Frobenius manifold is a tau-function of the extended nonlinear Schr\"odinger hierarchy, an extension of a particular rational reduction of the Kadomtsev--Petviashvili hierarchy. We prove a version of their conjecture specializing the Givental--M…